﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TSP
{
    class Graph
    {
        public int verticesCount;
        public List<Vertex> vertices;
        public List<Edge> edges;

        public Graph(int n)
        {
            if (n >= 100)
            {
                throw new System.ArgumentException("Too many vertices. Max is 100");
            }
            edges = new List<Edge>();
            verticesCount = n;
            vertices = generateVertices(n);
            generateEdges();
        }

        public Graph(List<Vertex> vertices)
        {
            verticesCount = vertices.Count;
            this.vertices = vertices;
            edges = new List<Edge>();
            generateEdges();
        }

        public Graph(Graph g)
        {
            verticesCount = g.verticesCount;
            edges = new List<Edge>();
            vertices = g.vertices;
            foreach (Vertex v in vertices)
            {
                v.Neighbours.Clear();
            }
        }
        public Graph()
        {
            edges = new List<Edge>();
            vertices = new List<Vertex>();
        }

        /// <summary>
        /// Function used to generate isloated vertices
        /// </summary>
        /// <param name="n">Number of vertices to generate</param>
        /// <returns>List of generated vertices</returns>
        private List<Vertex> generateVertices(int n)
        {
            List<Vertex> _vertices = new List<Vertex>();

            
            Random ran = new Random(DateTime.Now.Millisecond);
            for (int i = 0; i < n; i++)
            {
                int x = 0;
                int y = 0;
                
                bool exist = true;
                while (exist)
                {
                    x = ran.Next(0,10);
                    y = ran.Next(0,10);
                    if (_vertices.Count != 0)
                    {
                        int j = 0;
                        foreach (Vertex v in _vertices)
                        {
                            if (v.Position.X == x && v.Position.Y == y)
                            {
                                break;
                            }
                            else
                            {
                                j++;
                            }
                        }
                        if (j == _vertices.Count)
                        {
                            exist = false;
                        }
                    }
                    else
                    {
                        exist = false;
                    }
                }
                _vertices.Add(new Vertex(new System.Drawing.Point(x,y)));
            }
            return _vertices;
        }

        /// <summary>
        /// Generates edges for complete graph
        /// </summary>
        private void generateEdges()
        {
            foreach (Vertex _from in vertices)
            {
                foreach (Vertex to in vertices)
                {
                    if (_from == to)
                    {
                        continue;
                    }
                    else
                    {
                        double w = Math.Sqrt(Math.Pow((to.Position.X - _from.Position.X), 2) + Math.Pow((to.Position.Y - _from.Position.Y), 2));
                        _from.addEdge(to, w);
                        Edge res = (from e in edges where (e.From == _from && e.To == to) || (e.From == to && e.To == _from) select e).FirstOrDefault();
                        if (res == null)
                        {
                            edges.Add(new Edge(_from, to, w));
                        }
                    }
                }
            }
        }
        /// <summary>
        /// Prints all edges in the graph
        /// </summary>
        /// <returns></returns>
        public static string printEdges(Graph g)
        {
            string output = "Edges: \n";
            foreach (Edge e in g.edges)
            {
                output += e.print();
            }
            return output;
        }

        /// <summary>
        /// Prints graph
        /// </summary>
        /// <returns></returns>
        public static string print(Graph g)
        {
            string output = "Vertices: ";
            foreach (Vertex v in g.vertices)
            {
                output += v.print();
            }
            return output;
        }

        /// <summary>
        /// Kruslal's algorithm for finding Minimal Spanning Tree
        /// </summary>
        /// <returns>Minimal spanning tree </returns>
        public Graph kruskalMST(Graph g)
        {
            //sort egdes by weight
            List<Edge> sortedEdges = new List<Edge>(g.edges);
            sortedEdges.Sort((x, y) => x.Weight.CompareTo(y.Weight));
            
            //create copy of g without edges
            Graph mst = new Graph(g);
            
            //give each vertex different color
            int c = 0;
            foreach (Vertex v in mst.vertices)
            {
                v.Color = c;
                c++;
            }

            //createing MST
            int n = 0;
            Edge me;
            while (n < mst.verticesCount - 1 && sortedEdges.Count != 0)
            {
                //take first edge and remowe it form list
                me = sortedEdges.ElementAt(0);
                sortedEdges.RemoveAt(0);
                //check if selected edge connects different components - use Color propoerties
                if (me.From.Color != me.To.Color)
                {
                    //add edge to MST
                    Vertex v1 = (from v in mst.vertices where v == me.From select v).FirstOrDefault();
                    v1.addEdge(me.To, me.Weight);
                    Vertex v2 = (from v in mst.vertices where v == me.To select v).FirstOrDefault();
                    v2.addEdge(me.From, me.Weight);
                    mst.edges.Add(me);
                    //change color of each added vertex to component
                    v2.Color = v1.Color;
                    recolor(v2.Neighbours);
                    ++n;
                }
            }
            return mst;
        }

        /// <summary>
        /// Recolores vertices - used in Kruskal's algorithm
        /// </summary>
        /// <param name="edges">Listo of edges with vertices to recolor</param>
        private void recolor(List<Edge> edges)
        {
            foreach (Edge e in edges)
            {
                if (e.To.Color != e.From.Color)
                {
                    e.To.Color = e.From.Color;
                    recolor(e.To.Neighbours);
                }
            }
        }
    }
}
